Lucky numbers in a matrix¶
Time: O(MxN); Space: O(M+N); easy
Given a M * N matrix of distinct numbers, return all lucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: matrix = [[3,7,8], [9,11,13], [15,16,17]]
Output: [15]
Explanation:
is the only lucky number since it is the minimum in its row and the maximum in its column
Example 2:
Input: matrix = [[1,10,4,2], [9,3,8,7], [15,16,17,12]]
Output: [12]
Explanation:
is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 3:
Input: matrix = [[7,8], [1,2]]
Output: [7]
Notes:
len(matrix) = m
len(matrix[i]) = n
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.
Hints:
Find out and save the minimum of each row and maximum of each column in two lists.
Then scan through the whole matrix to identify the elements that satisfy the criteria.
[5]:
class Solution1(object):
def luckyNumbers (self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
rows = list(map(min, matrix))
cols = list(map(max, zip(*matrix)))
return [cell for i, row in enumerate(matrix)
for j, cell in enumerate(row) if rows[i] == cols[j]]
[6]:
s = Solution1()
matrix = [[3,7,8], [9,11,13], [15,16,17]]
assert s.luckyNumbers(matrix) == [15]
matrix = [[1,10,4,2], [9,3,8,7], [15,16,17,12]]
assert s.luckyNumbers(matrix) == [12]
matrix = [[7,8], [1,2]]
assert s.luckyNumbers(matrix) == [7]
[7]:
class Solution2(object):
def luckyNumbers (self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
return list(set(map(min, matrix)) &
set(map(max, zip(*matrix))))
[8]:
s = Solution2()
matrix = [[3,7,8], [9,11,13], [15,16,17]]
assert s.luckyNumbers(matrix) == [15]
matrix = [[1,10,4,2], [9,3,8,7], [15,16,17,12]]
assert s.luckyNumbers(matrix) == [12]
matrix = [[7,8], [1,2]]
assert s.luckyNumbers(matrix) == [7]